<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8"> <meta name="viewport" content="width=device-width">
    <title>X3C-1 与广义划分问题的NP完全性证明</title>
    <meta name="viewport" content="width=device-width,initial-scale=1, shrink-to-fit=no">
    <!-- Bootstrap CSS -->
    <link rel="stylesheet"
          href="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/css/bootstrap.min.css"
          integrity="sha384-9aIt2nRpC12Uk9gS9baDl411NQApFmC26EwAOH8WgZl5MYYxFfc+NcPb1dKGj7Sk"
          crossorigin="anonymous">
    <link rel="stylesheet"
          href="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/styles/androidstudio.min.css">
<!--    <link rel="stylesheet" href="/web_template_css.css">-->
    <!-- this is highlight.js -->
    <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
    <script id="MathJax-script" async
            src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
    </script>
    <script  src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.slim.min.js"
    integrity="sha384-DfXdz2htPH0lsSSs5nCTpuj/zy4C+OGpamoFVy38MVBnE+IbbVYUew+OrCXaRkfj" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/popper.js@1.16.0/dist/umd/popper.min.js"
    integrity="sha384-Q6E9RHvbIyZFJoft+2mJbHaEWldlvI9IOYy5n3zV9zzTtmI3UksdQRVvoxMfooAo" crossorigin="anonymous"></script>
    <script src="https://cdn.jsdelivr.net/npm/bootstrap@4.5.0/dist/js/bootstrap.min.js"
    integrity="sha384-OgVRvuATP1z7JjHLkuOU7Xw704+h835Lr+6QL9UvYjZE3Ipu6Tp75j7Bh/kR0JKI" crossorigin="anonymous"></script>
    <script src="//cdnjs.cloudflare.com/ajax/libs/highlight.js/10.5.0/highlight.min.js"></script>
    <style>
      img{
        display: block;
        height: auto;
        max-width: 100%;
      }
    </style>
  </head>
  <body>
    <nav class="navbar navbar-expand-lg navbar-light bg-light">
        <a class="navbar-brand" href="#">kvrmnks</a>
        <button class="navbar-toggler" type="button" data-toggle="collapse" data-target="#navbarNav" aria-controls="navbarNav" aria-expanded="false" aria-label="Toggle navigation">
          <span class="navbar-toggler-icon"></span>
        </button>
        <div class="collapse navbar-collapse" id="navbarNav">
          <ul class="navbar-nav">
            <li class="nav-item active">
              <a class="nav-link" href="./../../../../../index.html" target="_self">Home <span class="sr-only">(current)</span></a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../blog.html">Blog</a>
            </li>
            <li class="nav-item">
              <a class="nav-link" href="./../../../../../about.html">About</a>
            </li>
          </ul>
        </div>
      </nav>



    <div class='container'>
      <h2>X3C-1 与广义划分问题的NP完全性证明</h2>

<hr>

<p>老师上课留的作业</p>

<p>还蛮简单的（</p>

<hr>

<h3>X3C-1问题</h3>

<p>首先你需要知道什么是X3C问题（假装你知道了，其实是我懒得写了</p>

<p>X3C-1问题是任意两个元素的交的大小小于等于1</p>

<h3>证明</h3>

<p>我们尝试用X3C来归约到X3C-1来证明这件事情。</p>

<p>其实蛮简单的，假设\((a,b,c)\)是X3C集合的一个元素。</p>

<p>我们把它拆成以下5个元素</p>

<p>\[(a, e1, e2) \\ (b, e3, e4) \\ (c, e5, e6) \\ (e1, e3, e5) \\ (e2, e4, e6)\]</p>

<p>正确性显然（</p>

<h3>广义划分问题</h3>

<p>狭义的划分问题是将集合里的元素划分成两个部分，每个部分的和相等</p>

<p>而广义划分问题便是使得两个部分保持1:2的关系</p>

<h3>证明</h3>

<p>尝试从划分问题归约到这个问题。</p>

<p>假设原集合为S</p>

<p>加入\(\frac{3}{2}S\)与\(\frac{7}{2}S\)两个元素，正确性显然（</p>


    </div>
    <script>
      hljs.initHighlightingOnLoad()
    </script>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/highlightjs-line-numbers.js/2.5.0/highlightjs-line-numbers.min.js"></script>
  <script>
      hljs.initHighlightingOnLoad();
      hljs.initLineNumbersOnLoad();
  </script>
  </body>
</html>